import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val=x;
        next=null;
    }
}

public class LinkedListCycleII {
    public static ListNode detectCycle(ListNode head){
        if(head == null) return null;
        
        ListNode p = head;
        HashSet<ListNode> set = new HashSet<ListNode>();

        while(p!=null){
            if(set.contains(p)){
                return p;
            }
            else {
                set.add(p);
            }
        }

        return null;
    }
    
    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        ListNode n1 = new ListNode(2);
        ListNode n2 = new ListNode(3);
        ListNode n3 = new ListNode(4);

        node.next = n1;
        n1.next = n2;
        n2.next = n3;
        n3.next = n1;

        System.out.println(detectCycle(node).val);
    }
}